package week07

// 5. 最长回文子串
// https://leetcode-cn.com/problems/longest-palindromic-substring/

func longestPalindrome(s string) string {
	var preH = make([]int32, len(s)+1)
	var sufH = make([]int32, len(s)+2)
	var p131 = make([]int32, len(s)+1)
	p131[0] = 1
	for i := 1; i < len(preH); i++ {
		preH[i] = preH[i-1] * b + int32(s[i-1] - '0' + 1)
		p131[i] = p131[i-1] * b
	}
	for i := len(sufH)-2; i > 0; i-- {
		sufH[i] = sufH[i+1] * b + int32(s[i-1] - '0' + 1)
	}

	var calcPre = func(l, r int) int32 {
		return preH[r] - preH[l-1] * p131[r-l+1]
	}

	var calcSuf = func(l, r int) int32 {
		return sufH[l] - sufH[r+1] * p131[r-l+1]
	}

	var isPalindrome = func(l, r int) bool {
		if l < 0 || r >= len(s) {
			return false
		}
		if l > r {
			return true
		}
		return calcPre(l+1, r+1) == calcSuf(l+1, r+1)
	}

	// aba
	var ans = ""
	for center := 0; center < len(s); center++ {
		var lenL, lenR = 0, len(s)-1
		for lenL < lenR {
			var mid = (lenL + lenR + 1) / 2
			var l, r = center - mid, center + mid
			if isPalindrome(l, r) {
				lenL = mid
			} else {
				lenR = mid-1
			}
		}
		if len(ans) < lenL * 2 + 1 {
			ans = s[center-lenL : center+lenL+1]
		}
	}

	// bb
	for center := 0; center < len(s); center++ {
		var lenL, lenR = 0, len(s)-1
		for lenL < lenR {
			var mid = (lenL + lenR + 1) / 2
			var l, r = center - mid + 1, center + mid
			if isPalindrome(l, r) {
				lenL = mid
			} else {
				lenR = mid - 1
			}
		}
		if len(ans) < lenL * 2 {
			ans = s[center-lenL+1 : center+lenL+1]
		}
	}
	return ans
}

const b int32 = 131
const p int32 = 1e9 + 7